"Bubble Up" (or siftUp) is the algorithm for restoring the heap property after an insertion.

  • After placing a new node, compare it with its parent.
  • If the node is larger than its parent (in a max-heap), swap them.
  • Repeat this process: keep comparing the node with its new parent and swapping until it's smaller than its parent, or it reaches the root.
  • This ensures the heap property is restored along the path from the new node to the root.

Complexity

The number of swaps is at most the height of the tree, making this an O(log n) operation.

100 19 36 17 3 101
Array Representation
def bubble_up(heap, index):
    parent_index = (index - 1) // 2
    # While not root and child > parent
    while index > 0 and heap[index] > heap[parent_index]:
        # Swap child and parent
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        # Move up to the parent's position
        index = parent_index
        parent_index = (index - 1) // 2